#include <stdio.h>
#include <malloc.h>
typedef int elementype;
typedef struct LinkedStackNode
{
    elementype data;
    struct LinkedStackNode *next;
} LinkedStackNode;

// 初始化头节点
LinkedStackNode *Init_LinkedStack()
{
    LinkedStackNode *head = (LinkedStackNode *)malloc(sizeof(LinkedStackNode));
    if (head == NULL)
    {
        return 0;
    }
    else
    {
        head->next = NULL;
        return head;
    }
}

// 判栈空
int LinkedStack_Empty(LinkedStackNode *head)
{
    if (head == NULL)
    {
        return 1;
    }

    return 0;
}

// 入栈
int Push_LinkStack(LinkedStackNode *head, elementype x)
{
    // 创建一个临时节点用于存储接受x数值，并插入新的首节点中。
    LinkedStackNode *s = Init_LinkedStack();
    s->data = x;
    s->next = head->next;
    head->next = s;

    return 1;
}

// 出栈
int Pop_LinkedStack(LinkedStackNode *head, elementype *x)
{
    if (LinkedStack_Empty(head))
    {
        return 0;
    }

    // 创建一个临时变量存首节点
    LinkedStackNode *temp = head->next;
    head->next = temp->next;
    *x = temp->data;
    free(temp);
    return 1;
}

// 取栈顶元素
elementype GetTop_LinkedStack(LinkedStackNode *head)
{
    if (LinkedStack_Empty(head))
    {
        return 0;
    }
    return head->next->data;
}

// 头插法创建
LinkedStackNode *Create_LinkedStackF(int *arr, int length)
{
    // 创建一个头结点
    LinkedStackNode *head = Init_LinkedStack();

    for (size_t i = 0; i < length; i++)
    {
        // 创建一个待插入节点
        LinkedStackNode *s = Init_LinkedStack();
        s->next = head->next;
        s->data = arr[i];
        head->next = s;
    }

    return head;
}

// 打印链栈
int Print_LinkedStack(LinkedStackNode *head)
{
    for (LinkedStackNode *p = head->next; p != NULL; p = p->next)
    {
        printf("%3d", p->data);
    }
    putchar('\n');

    return 1;
}

int main()
{
    // 测试所有基本运算的函数
    int arr[] = {11, 22, 33, 44, 55};
    int length = sizeof(arr) / sizeof(arr[0]);
    int query_reuslt;
    LinkedStackNode *head = Create_LinkedStackF(arr, length);
    printf("创建一个栈:");
    Print_LinkedStack(head);
    Push_LinkStack(head,56);
    printf("向栈中插入数据:");
    Print_LinkedStack(head);
    Pop_LinkedStack(head,&query_reuslt);
    printf("出栈之后:");
    Print_LinkedStack(head);
    printf("取栈顶元素:");
    query_reuslt = GetTop_LinkedStack(head);
    printf("%d",query_reuslt);
    return 0;
}